#include <stdlib.h>
#include <stdio.h>
#include "Huffman.h"

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC,char * tokens,float * weights,int n){
    if (n<=1) return;
    int i,m = 2*n -1;
    HT = malloc((m+1)*sizeof(HFNode));
    HT[0].weight = 1;
    for (i=1;i<n+1;++i){
        HT[i].token = tokens[i-1];
        HT[i].weight = weights[i-1];
        HT[i].parent = HT[i].lchild = HT[i].token = 0;
        // printf("%c %f\n",HT[i].token,HT[i].weight);
    } 
    int l,p,q;
    for (l=n;l<m;++l){
        p=q=0;
        for (int i=1;i<l+1;++i){
            if (HT[i].parent!=0) continue;
            if (HT[i].weight<HT[q].weight){
                q=i;
                if (HT[i].weight<HT[p].weight){
                    q=p,p=i;
                }
            }
        }
        HT[p].parent=HT[q].parent=l+1;
        HT[l+1].parent=0;
        HT[l+1].lchild=p;
        HT[l+1].rchild=q;
        HT[l+1].weight=HT[p].weight+HT[q].weight;
        HT[l+1].token='-';
    }
    // printf("%f\n",HT[m].weight);
    // printf("%d\n",HT[m].lchild);
    

}